package com.leetcode.hashtable;

import java.util.*;

/**
 * @author: ZhouBert
 * @date: 2019/9/25
 * @description: 1. 两数之和
 * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
 * <p>
 * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
 * <p>
 * 示例:
 * 给定 nums = [2, 7, 11, 15], target = 9
 * <p>
 * 因为 nums[0] + nums[1] = 2 + 7 = 9
 * 所以返回 [0, 1]
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/two-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class TwoSum1 {

	/**
	 * 只有两个数！--O(n2)--这个复杂度有点高了
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int[] twoSum(int[] nums, int target) {
		///1.边界条件判断
		if (nums == null || nums.length < 2) {
			return null;
		}
		int[] result = new int[2];
		///2.排序	如果只有一种组合，就不需要排序，而且需要返回的是原来的位置
		///Arrays.sort(nums);
		///3.双指针 X->可能是改成双重循环了
		int right = 1;
		for (int i = 0; i < nums.length; i++) {
			for (int j = i + 1; j < nums.length; j++) {
				if (nums[i] + nums[j] == target) {
					result[0] = i;
					result[1] = j;
					return result;
				}
			}
		}
		return null
				;
	}

	/**
	 * 利用哈希值计算
	 * TODO：SKILL-将补数存入哈希表！
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int[] twoSum2(int[] nums, int target) {
		int[] indexs = new int[2];

		// 建立k-v ，一一对应的哈希表
		HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>();
		for (int i = 0; i < nums.length; i++) {
			if (hash.containsKey(nums[i])) {
				indexs[0] = i;
				indexs[1] = hash.get(nums[i]);
				return indexs;
			}
			// 将数据存入 key为补数 ，value为下标
			hash.put(target - nums[i], i);
		}
		// // 双重循环 循环极限为(n^2-n)/2
		// for(int i = 0; i < nums.length; i++){
		//     for(int j = nums.length - 1; j > i; j --){
		//         if(nums[i]+nums[j] == target){
		//            indexs[0] = i;
		//            indexs[1] = j;
		//            return indexs;
		//         }
		//     }
		// }
		return indexs;
	}

	/**
	 * hash key重复的问题--如何保持key的唯一性--用索引坐标来代替 X--这样不行，太复杂了
	 * TODO:实际是通过在 hash 记录补数作为KEY，以及正数作为VALUE!
	 *
	 * @param nums
	 * @param target
	 * @return
	 */
	public static int[] twoSum2_1(int[] nums, int target) {
		///1.边界条件判断
		if (nums == null || nums.length < 2) {
			return null;
		}
		int[] result = new int[2];
		Map<Integer, Integer> map = new HashMap<>();
		for (int i = 0; i < nums.length; i++) {
			///1.是否存在补数
			if (map.containsKey(nums[i])){
				result[0]=i;
				result[1]=map.get(nums[i]);
				return result;
			}else {
				map.put(target-nums[i],i);
			}
		}

		return null;
	}

	public static void main(String[] args) {
		int[] ints = new int[]{2, 7, 11, 15};
		ints = new int[]{2, 5, 5, 11};
		int target = 9;
		target = 10;
		int[] ints1 = twoSum(ints, target);
		int[] ints2 = twoSum2(ints, target);
		int[] ints3 = twoSum2_1(ints, target);
		System.out.println(Arrays.toString(ints1));
		System.out.println(Arrays.toString(ints2));
		System.out.println(Arrays.toString(ints3));
	}
}
